陶哲轩再逼近60年几何学难题!周期性密铺问题又获新突破
编辑:Aeneas
编辑:Aeneas
【新智元导读】关于60年的几何学难题周期性密铺问题,陶哲轩最近又有新突破了。
陶哲轩一直在研究的周期性密铺问题,又有新突破了。
9月18日,陶哲轩和Rachel Greenfeld将预印本论文《平移单密铺的不可判定性 (Undecidability of translational monotilings)》上传到了arXiv。
这篇论文的主要结论是,如果网格的维数是无界的,那么确定网格的有限子集是否可以平铺该网格的周期子集的问题,就是不可判定的。
要知道,此问题在维度1和维度2中是可判定的。
陶哲轩表示,有点奇怪的是,文中所证明的大多数组件都跟流行的游戏类似——
多米诺骨牌的密铺类似物,数独,电脑游戏「俄罗斯方块」,甚至连儿童游戏「Fizz buzz」都出现了。
为什么研究一个数学问题,会涉及到这么多游戏呢?陶哲轩也无法解释。
平移单密铺的不可判定性
在上篇论文中,他们构建了一个高维网格
(因此单密铺
这就反驳了Stein、Grunbaum-Shephard和Lagarias-Wang的周期性密铺猜想,他们断言这种非周期性密铺单体不存在。
(「帽子单密铺」是一种最近发现的非周期等距单密铺
激发陶哲轩和Rachel Greenfeld这个猜想的原因之一,是数学家Hao Wang的观察。
他发现,如果周期密铺猜想为真,那么平移密铺问题在算法上是可判定的——
有一个图灵机,对于
这是因为如果存在周期性密铺,就可以通过计算机搜索找到它。
如果根本不存在密铺,那么通过紧致性定理可知,存在一些有限的
周期性密铺猜想断言这是仅有的两种可能的情况,从而给出了可判定性。
另一方面,Wang的论点是不可逆的:周期性密铺猜想的失败,并不自动意味着平移单密铺问题的不可判定性,因为它不排除存在一些其他算法来确定密铺,这种密铺可以不依赖于周期性密铺的存在。
(例如,即使有新发现的帽子和幽灵密铺,对于
本文的主要结果解决了这个问题(有一个警告):
定理1
不存在任何算法,对于
需要注意的是,必须使用
另外,陶哲轩和Rachel Greenfeld还注意到,当
对于任何
由于算法不可判定性和逻辑不可判定性(也称为逻辑独立性)之间存在众所周知的联系,此定理还暗示了存在一个(原则上明确可描述的)维度
作为这种方法的结果,我们也可以在这里用「几乎二维」群
接下来,描述证明的一些主要思想。
证明某个问题不可判定的常用方法是,将已知不可判定的其他问题「编码」到原始问题中,这样,任何判定原始问题的算法也能判定嵌入的问题。
因此,我们将 Wang密铺问题编码为单密铺问题
问题2(Wang密铺问题)
给定一个有限的王氏密铺集合
Berger曾给出一个著名的结果,即这个问题是不可判定的。
将这一问题嵌入高维平移单密铺问题需要经过一些中间问题。
首先,我们可以很容易地将王氏密铺问题嵌入到一个类似的问题中,我们称之为多米诺骨牌问题:
问题 3(多米诺骨牌问题)
给定一个水平(或垂直)的多米诺骨牌的有限集合
事实上,我们只需要将每个王氏密铺作为一个单独的「点」插入,并定义多米诺骨牌集
接下来,将多米诺骨牌问题嵌入到数独问题中:
问题 4(数独问题)
给定列宽
这篇论文最新颖的部分是证明了多米诺骨牌问题确实可以嵌入到数独问题中。
将数独问题嵌入到单密铺问题中,源于之前论文中修改的方法。
这些论文也引入了数独问题的版本,并创造了一种「密铺语言」,可用于把各种问题(包括数独问题)「编码」为单密铺问题。
要将多米诺骨牌问题编码为数独问题,我们需要获取一个多米诺函数
这种做法并不是很显而易见,但是在Emmanuel Jeandel的帮助下,陶哲轩和Rachel Greenfeld改编了Aanderaa和Lewis的一些想法,某些层次结构被用来将一个问题编码另一个问题。
在这里,我们解释分层结构
然后,通过公式
其中
(
在
最终分量
有趣的是,不知为何,这里的装饰基本上遵循了儿童游戏「Fizz buzz」的规则。
让我知道你在看
复制搜一搜分享收藏划线